#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int len = s.size();
        vector<bool> dp(len + 1, false);
        dp[0] = true;

        for (int i = 1; i <= len; i++) {
            for (auto word : wordDict) {
                int m = word.size();
                if (i - m >= 0 && s.substr(i - m, m) == word) {
                    dp[i] = dp[i - m];
                    if (dp[i] == true)break;
                }
            }
        }
        return dp[len];
    }

};